package com.lims.algorithm.algset.tree;

import java.util.Stack;

/**
 * <描述:> 二叉查找树
 *
 * @author lims
 * @date 2020-04-17 22:39
 */
public class BSTree<T extends Comparable<T>> {
    /**
     * 二叉查找树结点
     *
     * @param <T>
     */
    public static class BSTNode<T extends Comparable<T>> {
        // 关键字
        T key;
        // 指向当前结点的左孩子
        BSTNode<T> left;
        // 指向当前结点的右孩子
        BSTNode<T> right;
        // 指向当前结点的父结点
        BSTNode<T> parent;

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 二叉查找树根结点
     */
    private BSTNode<T> bstRoot;

    /**
     * 向当前二叉查找树中插入key的结点
     *
     * @param key 插入结点关键字
     */
    public void insert(T key) {
        BSTNode<T> insertBstNode = new BSTNode<>(key, null, null, null);
        if (insertBstNode != null) {
            insertBSTNode(this, insertBstNode);
        }
    }

    /**
     * 给二叉树查找树插入新结点
     *
     * @param bsTree           二叉查找树
     * @param insertBstKeyNode 要插入的结点
     */
    private void insertBSTNode(BSTree<T> bsTree, BSTNode<T> insertBstKeyNode) {
        // 结点key大小比较标记
        int cmpFlag;
        // 追踪当前结点
        BSTNode<T> currentNode;

        if (bsTree.bstRoot == null) {
            bsTree.bstRoot = insertBstKeyNode;
        } else {
            currentNode = bsTree.bstRoot;
            while (true) {
                // 插入结点和当前结点比较大小
                cmpFlag = insertBstKeyNode.key.compareTo(currentNode.key);
                if (cmpFlag > 0) {
                    // 当前结点右子为空时挂到当前结点的右子
                    if (currentNode.right == null) {
                        currentNode.right = insertBstKeyNode;
                        insertBstKeyNode.parent = currentNode;
                        return;
                    } else {
                        // 当前结点右子不为空时，current指针右移
                        currentNode = currentNode.right;
                    }
                } else if (cmpFlag < 0) {
                    if (currentNode.left == null) {
                        currentNode.left = insertBstKeyNode;
                        insertBstKeyNode.parent = currentNode;
                        return;
                    } else {
                        currentNode = currentNode.left;
                    }
                } else {
                    // throw new Exception("二叉查找树中已经存在key：" + insertBstKeyNode.key);
                    System.out.println("二叉查找树中已经存在key：" + insertBstKeyNode.key);
                    return;
                }
            }
        }
    }

    /**
     * 先序遍历（递归）
     */
    public void preOrderRecur() {
        preOrderBsTreeRecur(this.bstRoot);
    }

    /**
     * 先序遍历二叉树
     *
     * @param bstRoot 根结点
     */
    private void preOrderBsTreeRecur(BSTNode<T> bstRoot) {
        if (bstRoot != null) {
            System.out.print(bstRoot.key + " ");
            preOrderBsTreeRecur(bstRoot.left);
            preOrderBsTreeRecur(bstRoot.right);
        }
    }

    /**
     * 先序遍历（非递归）
     */
    public void preOrderNonRecur() {
        preOrderBsTreeNonRecur(this.bstRoot);
    }

    /**
     * 先序遍历（非递归 单栈法）
     *
     * @param bstRoot
     */
    private void preOrderBsTreeNonRecur(BSTNode<T> bstRoot) {
        Stack<BSTNode<T>> stack = new Stack<>();
        while (true) {
            if (bstRoot != null) {
                System.out.print(bstRoot.key + " ");
                stack.push(bstRoot);
                bstRoot = bstRoot.left;
            } else {
                if (stack.isEmpty()) {
                    break;
                }
                bstRoot = stack.pop().right;
            }
        }
    }

    /**
     * 先序遍历（递归）
     */
    public void inOrderRecur() {
        inOrderBsTreeRecur(this.bstRoot);
    }

    /**
     * 先序遍历（递归）
     *
     * @param bstRoot
     */
    private void inOrderBsTreeRecur(BSTNode<T> bstRoot) {
        if (bstRoot != null) {
            inOrderBsTreeRecur(bstRoot.left);
            System.out.print(bstRoot.key + " ");
            inOrderBsTreeRecur(bstRoot.right);
        }
    }

    /**
     * 中序遍历（非递归）
     */
    public void inOrderNonRecur() {
        inOrderBsTreeNonRecur(this.bstRoot);
    }

    /**
     * 中序遍历（非递归，单栈法）
     *
     * @param bstRoot
     */
    private void inOrderBsTreeNonRecur(BSTNode<T> bstRoot) {
        Stack<BSTNode<T>> stack = new Stack<>();
        while (true) {
            while (bstRoot != null) {
                stack.push(bstRoot);
                bstRoot = bstRoot.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            System.out.print(stack.peek().key + " ");
            bstRoot = stack.pop().right;
        }
    }

    /**
     * 后序遍历（递归）
     */
    public void postOrderRecur() {
        postOrderBsTreeRecur(this.bstRoot);
    }

    /**
     * 后序遍历（递归）
     *
     * @param bstRoot
     */
    private void postOrderBsTreeRecur(BSTNode<T> bstRoot) {
        if (bstRoot != null) {
            postOrderBsTreeRecur(bstRoot.left);
            postOrderBsTreeRecur(bstRoot.right);
            System.out.print(bstRoot.key + " ");
        }
    }

    /**
     * 后序遍历本类对象（非递归，单栈法）
     */
    public void postOrderTwoStack() {
        postOrderBsTreeTwoStask(this.bstRoot);
    }

    /**
     * 后序遍历（非递归，双栈法）
     *
     * @param bstRoot
     */
    private void postOrderBsTreeTwoStask(BSTNode<T> bstRoot) {
        Stack<BSTNode<T>> stackCache = new Stack<>();
        // 后序遍历顺序倒排序的栈
        Stack<BSTNode<T>> stackPostNode = new Stack<>();
        if (bstRoot == null) {
            return;
        }
        // 初始，根结点入缓存栈
        stackCache.push(bstRoot);
        while (!stackCache.isEmpty()) {
            // 弹出缓存栈顶，入后序栈
            bstRoot = stackCache.pop();
            stackPostNode.push(bstRoot);
            // 左右子结点入栈，取出时按右-》左顺序
            if (bstRoot.left != null) {
                stackCache.push(bstRoot.left);
            }
            if (bstRoot.right != null) {
                stackCache.push(bstRoot.right);
            }
        }
        // 打印后序栈
        while (!stackPostNode.isEmpty()) {
            System.out.print(stackPostNode.pop().key + " ");
        }
    }

    /**
     * 后序遍历本类对象（非递归，单栈法）
     */
    public void postOrderSingleStack() {
        postOrderBsTreeSingleStack(this.bstRoot);
    }

    /**
     * 后序遍历二叉树（非递归，单栈法）
     * <p>
     * 思路：
     * 1.向左循环压栈，遇到空时判断
     * 2.判断栈顶的右结点状态。根据为空或不为空状态，将root指针指向栈顶或者右结点
     * 3.root指向右结点时，再判断栈顶对应右结点状态，判断右结点状态和root指针关系，确定继续压栈操作or作为最右链路依次向上弹出
     * <p>
     * PS:最右链路向上弹出到底后，为保证已经出栈结点不重复压栈，root重置为null（只判断栈顶结点）
     *
     * @param bstRoot
     */
    private void postOrderBsTreeSingleStack(BSTNode<T> bstRoot) {
        Stack<BSTNode<T>> stack = new Stack<>();
        while (true) {
            if (bstRoot != null) {
                stack.push(bstRoot);
                bstRoot = bstRoot.left;
            } else {
                if (stack.isEmpty()) {
                    return;
                }
                // 栈顶结点的右孩子不为空时，按后序规则，指针移动到右孩子上继续入栈
                if (stack.peek().right != null) {
                    bstRoot = stack.peek().right;
                } else {
                    // 弹出栈顶
                    bstRoot = stack.pop();
                    System.out.print(bstRoot.key + " ");
                    if (stack.isEmpty()) {
                        return;
                    }
                    // 处于右侧的结点依次循环弹出
                    while (stack.peek().right == bstRoot) {
                        bstRoot = stack.pop();
                        System.out.print(bstRoot.key + " ");
                        if (stack.isEmpty()) {
                            return;
                        }
                    }
                    // 弹完左孩子时，为了不重复之前的左孩子入栈，指针置为null
                    if (!stack.isEmpty()) {
                        bstRoot = null;
                    }
                }
            }
        }
    }

    /**
     * 查找"二叉树x"中键值为key的节点（递归）
     *
     * @param key
     * @return
     */
    public BSTNode<T> searchRecur(T key) {
        return searchRecur(this.bstRoot, key);
    }

    private BSTNode<T> searchRecur(BSTNode<T> bstRoot, T key) {
        if (bstRoot == null) {
            return bstRoot;
        }
        int cmpFlag = key.compareTo(bstRoot.key);
        if (cmpFlag > 0) {
            searchRecur(bstRoot.right, key);
        } else if (cmpFlag < 0) {
            searchRecur(bstRoot.left, key);
        } else {
            return bstRoot;
        }
        return bstRoot;
    }

    /**
     * 查找"二叉树x"中键值为key的节点（非递归）
     *
     * @param key
     * @return
     */
    public BSTNode<T> search(T key) {
        return search(this.bstRoot, key);
    }

    private BSTNode<T> search(BSTNode<T> bstRoot, T key) {
        while (bstRoot != null) {
            int cmpFlag = key.compareTo(bstRoot.key);
            if (cmpFlag < 0) {
                bstRoot = bstRoot.left;
            } else if (cmpFlag > 0) {
                bstRoot = bstRoot.right;
            } else {
                return bstRoot;
            }
        }
        return null;
    }

    /**
     * 全局查找key结点（适用于普通二叉树）
     */
    public BSTNode<T> searchAll(T key) {
        return searchAll(this.bstRoot, key);
    }

    public BSTNode<T> searchAll(BSTNode<T> bstRoot, T key) {
        if (bstRoot == null) {
            return null;
        }
        if ((key.compareTo(bstRoot.key)) == 0) {
            return bstRoot;
        }
        BSTNode<T> leftSearch = searchAll(bstRoot.left, key);
        BSTNode<T> rightSearch = searchAll(bstRoot.right, key);

        if (leftSearch != null) {
            return leftSearch;
        }
        if (rightSearch != null) {
            return rightSearch;
        }
        return null;
    }

    /**
     * 查找最大值
     *
     * @return
     */
    public T findMaxReucr() {
        BSTNode<T> maximum = findMaxReucr(this.bstRoot);
        if (maximum != null) {
            return maximum.key;
        }
        return null;
    }

    /**
     * 查找最大结点：返回tree为根结点的二叉树的最大结点。
     *
     * @param bstRoot
     * @return
     */
    private BSTNode<T> findMaxReucr(BSTNode<T> bstRoot) {
        if (bstRoot == null) {
            return null;
        }
        while (bstRoot.right != null) {
            bstRoot = bstRoot.right;
        }
        return bstRoot;
    }

    /**
     * 最大值 递归
     *
     * @return
     */
    public BSTNode<T> findMax() {
        return findMax(this.bstRoot);
    }

    private BSTNode<T> findMax(BSTNode<T> bstRoot) {
        if (bstRoot == null) {
            return bstRoot;
        }
        BSTNode<T> leftMax = findMax(bstRoot.left);
        BSTNode<T> rightMax = findMax(bstRoot.right);

        if (leftMax == null && rightMax == null) {
            return bstRoot;
        }
        if (leftMax == null) {
            return bstRoot.key.compareTo(rightMax.key) > 0 ? bstRoot : rightMax;
        }
        if (rightMax == null) {
            return bstRoot.key.compareTo(leftMax.key) > 0 ? bstRoot : leftMax;
        }
        // 左右结点的最大值
        BSTNode<T> lrMax;
        return bstRoot.key.compareTo(
                (lrMax = leftMax.key.compareTo(rightMax.key) > 0 ? leftMax : rightMax).key
        ) > 0 ? bstRoot : lrMax;
    }

    /**
     * 查找最小值
     *
     * @return
     */
    public T findMin() {
        BSTNode<T> minimum = findMin(this.bstRoot);
        if (minimum != null) {
            return minimum.key;
        }
        return null;
    }

    /**
     * 查找最小结点：返回tree为根结点的二叉树的最大结点。
     *
     * @param bstRoot
     * @return
     */
    private BSTNode<T> findMin(BSTNode<T> bstRoot) {
        if (bstRoot == null) {
            return null;
        }
        while (bstRoot.left != null) {
            bstRoot = bstRoot.left;
        }
        return bstRoot;
    }

    /**
     * 二叉树深度
     *
     * @return
     */
    public int maxDepth() {
        return maxDepth(this.bstRoot);
    }

    /**
     * 二叉树深度
     *
     * @param bstRoot
     * @return
     */
    public int maxDepth(BSTNode<T> bstRoot) {
        if (bstRoot == null) {
            return 0;
        } else {
            int leftDepth = maxDepth(bstRoot.left);
            int rightDepth = maxDepth(bstRoot.right);
            return 1 + Math.max(leftDepth, rightDepth);
        }
    }

    /**
     * 查找结点的前驱
     * <p>
     * 节点的前驱：是该节点的左子树中的最大节点。
     * 节点的后继：是该节点的右子树中的最小节点。
     * <p>
     * 前驱结点：节点val值小于该节点val值并且值最大的节点
     * 后继节点：节点val值大于该节点val值并且值最小的节点
     * <p>
     * 前驱节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱节点；
     * 后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；
     *
     * @param bstRoot
     * @return
     */
    public BSTNode<T> predecessor(BSTNode<T> bstRoot) {
        // 前驱结点
        BSTNode<T> predecessor = bstRoot;
        BSTNode<T> current;

        if (bstRoot.left == null) {
            // 为父结点的右子时，父结点为前驱
            if (bstRoot.parent != null &&
                    bstRoot == bstRoot.parent.right) {
                return bstRoot.parent;
            } else {
                return null;
            }
        }

        // 左子树不为空
        current = bstRoot.left;
        while (current != null) {
            predecessor = current;
            current = current.right;
        }
        return predecessor;
    }

    /**
     * 后继结点
     *
     * @param bstRoot
     * @return
     */
    /**
     * 寻找后继结点
     * 1.无右子树时，父结点为后继结点
     * 2.有右子树时，为右子树上最小值（右子树上最左结点）
     *
     * @param bstRoot
     * @return
     */
    public BSTNode<T> successor(BSTNode<T> bstRoot) {
        // 后继结点
        BSTNode<T> successor = bstRoot;
        BSTNode<T> current;

        // 无右子树时，后继结点为父结点
        if (bstRoot.right == null) {
            if (bstRoot.parent != null &&
                    bstRoot == bstRoot.parent.left) {
                return bstRoot.parent;
            } else {
                return null;
            }
        }
        // 有右子树
        current = bstRoot.right;
        while (current != null) {
            successor = current;
            current = current.left;
        }
        return successor;
    }

    /**
     * 删除结点
     *
     * @param key
     */
    public Boolean remove(T key) {
        BSTNode<T> delNode, node;
        if ((delNode = search(this.bstRoot, key)) != null) {
            return remove(delNode);
        }
        return false;
    }

    /**
     * 删除结点分3大类：
     * 1.要删除节点有零个孩子，即叶子节点
     * （只需要将parent.left(或者是parent.right)设置为null，然后Java垃圾自动回收机制会自动删除current节点。）
     * <p>
     * 2.要删除节点有一个孩子
     * （只需要将parent.left(或者是parent.right)设置为curren.right(或者是current.left)即可）
     * <p>
     * 3.要删除节点有两个孩子
     * 3.1 后继节点为待删除节点的右子
     * （只需要将curren用successor替换即可，注意处理好current.left和successor.right.）
     * （注意：这种情况下，successor一定没有左孩子，一但它有左孩子，哪它必然不是current的后继节点。）
     * 3.2 后继节点位于待删除结点右子的左子树
     * 算法的步骤是：
     * successorParent.left=successor.right
     * successor.left=current.left
     * parent.left=seccessor
     * <p>
     * <p>
     * 3.2步骤
     * (1) 后继结点（替代删除结点）的右子改变挂点，挂到新位置（即后继结点的父结点）
     * (2) 后继结点（替代删除结点）挂新的左子（即待删除结点的左子）
     * (3) 后继结点（替代删除结点）挂新的右子（即后继结点的父结点）
     * <p>
     * (4) 后继结点替代待删除结点，待删除结点被删除
     *
     * @param delNode
     * @return
     */
    private Boolean remove(BSTNode<T> delNode) {
        // 需要删除的当前结点
        BSTNode<T> current = delNode;
        // 父结点
        BSTNode<T> parentNode = delNode.parent;

        if (search(bstRoot, current.key) == null) {
            System.out.println("没有此结点");
            return false;
        }

        // 要删除结点为叶子结点
        if ((current.left == null) && (current.right == null)) {
            if (current == bstRoot) {
                // 整棵树清空
                bstRoot = null;
            } else {
                // 为父结点的右子
                if (current.parent == parentNode.right) {
                    parentNode.right = null;
                    current.parent = null;
                } else {
                    parentNode.left = null;
                    current.parent = null;
                }
            }
        } else if (current.left == null) {
            // 删除结点只有一个右子
            if (current == bstRoot) {
                bstRoot = current.right;
                current.right.parent = bstRoot;
            } else if (current == parentNode.right) {
                // 删除结点为父结点的右子
                parentNode.right = current.right;
                current.right.parent = parentNode;
            } else {
                // 删除结点为父结点的左子
                parentNode.left = current.right;
                current.right.parent = parentNode;
            }
        } else if (current.right == null) {
            // 删除结点只有一个左子
            if (current == bstRoot) {
                bstRoot = current.left;
                current.left.parent = bstRoot;
            } else if (current == parentNode.right) {
                // 删除结点为父结点的右子
                parentNode.right = current.left;
                current.left.parent = parentNode;
            } else {
                // 删除结点为父结点的左子
                parentNode.left = current.left;
                current.left.parent = parentNode;
            }
        } else {
            // 删除结点有左右子，用 当前结点和“后继结点”的关系
            BSTNode<T> successor = successor(current);
            // 删除根结点
            if (current == bstRoot) {
                // 当后继结点为根结点的右子时
                if (successor == current.right) {
                    //  新根结点（后继结点）挂新的的左子树（即待删除根结点的左子树）
                    successor.left = current.left;
                    current.left.parent = successor;
                    // 新根结点
                    bstRoot = successor;
                    // GC回收旧根结点（新根结点的parent置为null）
                    bstRoot.parent = null;
                } else {
                    // 后继结点位于根结点右子的左子树上

                    //后继结点的父结点
                    BSTNode<T> successorParent = successor.parent;

                    // 新根结点（后继结点）的右子改变挂点（挂到后继结点的父结点上）
                    successorParent.left = successor.right;
                    successor.right.parent = successorParent;
                    // 新根结点（后继结点）挂新的的左子树（即待删除根结点的左子树）
                    successor.left = current.left;
                    current.left.parent = successor;
                    // 新根结点（后继结点）挂新的的右子树（即后继结点的父结点）
                    successor.right = successorParent;
                    successorParent.parent = successor;

                    // 新根结点
                    bstRoot = successor;
                    // GC回收旧根结点
                    bstRoot.parent = null;
                    return true;
                }

                return true;
            }

            /* 删除结点不为根结点时
             1.后继结点为删除结点的右子;
             2.后继结点位于删除结点右子的左子树上*/

            // 1.后继结点为删除结点的右子
            if (successor == current.right) {
                // 后继结点挂新的左子（即待删除结点的左子树）
                successor.left = current.left;
                current.left.parent = successor;

                // 父结点挂新的左（右）子树，后继结点替换待删除结点的位置
                if (current.parent == parentNode.right) {
                    // 待删除结点为父结点的右子
                    parentNode.right = successor;
                    successor.parent = parentNode;
                } else {
                    // 待删除结点为父结点的左子
                    parentNode.left = successor;
                    successor.parent = parentNode;
                }
            } else {
                // 2.后继结点位于删除结点右子的左子树上

                // 后继结点的父结点
                BSTNode<T> successorParent = successor.parent;
                // 后继结点（替代删除结点）的右子改变挂点，挂到新位置（即后继结点的父结点）
                successorParent.left = successor.right;
                successor.right.parent = successorParent;
                // 后继结点（替代删除结点）挂新的左子（即待删除结点的左子）
                successor.left = current.left;
                current.left.parent = successor;
                // 后继结点（替代删除结点）挂新的右子（即后继结点的父结点）
                successor.right = successorParent;
                successorParent.parent = successor;

                // 删除结点，后继结点替代待删除结点
                if (current == parentNode.left) {
                    parentNode.left = successor;
                    successor.parent = parentNode;
                } else {
                    parentNode.right = successor;
                    successor.parent = parentNode;
                }
            }

        }
        return true;
    }

    /**
     * 打印本类二叉树
     */
    public void print() {
        if (bstRoot != null) {
            print(this.bstRoot, bstRoot.key, 0);
        } else {
            System.out.println("二叉树为空");
        }
    }

    /**
     * 打印"二叉查找树"
     *
     * @param bstRoot   二叉查找树（根结点）
     * @param key       关键字
     * @param direction 结点位置
     *                  0：表示根结点；
     *                  -1：表示是父结点的左孩子；
     *                  1：表示是父结点的右孩子；
     */
    private void print(BSTNode<T> bstRoot, T key, int direction) {
        if (bstRoot != null) {
            if (direction == 0) {
                System.out.printf("%2d id root\n", bstRoot.key);
            } else {
                System.out.printf("%2d is %2d's %6s child\n",
                        bstRoot.key, key, direction == 1 ? "right" : "left");
            }
            print(bstRoot.left, bstRoot.key, -1);
            print(bstRoot.right, bstRoot.key, 1);
        }
    }

    /**
     * 销毁二叉树
     */
    public void clear() {
        this.bstRoot = null;
    }


    /*******************************分割线 测试程序***********************************/


    public static void main(String[] args) {
        /**
         * ------------------------39
         * -------------------/        \
         * ----------------24           64
         * --------------/     \      /    \
         * ------------23      30    53    70
         * ------------------ /  \    \      \
         * -----------------26   35    60    75
         * ------------------\               /
         * ------------------27             72
         */
        BSTree<Integer> bsTree = new BSTree<>();

        bsTree.insert(39);
        bsTree.insert(24);
        bsTree.insert(64);
        bsTree.insert(23);
        bsTree.insert(30);
        bsTree.insert(53);
        bsTree.insert(60);

        bsTree.insert(26);
        bsTree.insert(27);
        bsTree.insert(35);
        bsTree.insert(70);
        bsTree.insert(75);
        bsTree.insert(72);

        /*bsTree.insert(65);
        bsTree.insert(69);
        bsTree.insert(68);
        bsTree.insert(67);
        bsTree.insert(66);*/

        System.out.println("root结点：" + bsTree.bstRoot.key);

        System.out.println("先序遍历");
        bsTree.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        bsTree.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        bsTree.postOrderRecur();
        System.out.println();

        System.out.println("先序遍历非递归");
        bsTree.preOrderNonRecur();
        System.out.println();
        System.out.println("中序遍历非递归");
        bsTree.inOrderNonRecur();
        System.out.println();
        System.out.println("后序遍历非递归双栈法");
        bsTree.postOrderTwoStack();
        System.out.println();
        System.out.println("后序遍历非递归单栈法");
        bsTree.postOrderSingleStack();
        System.out.println();

        bsTree.print();

        BSTNode<Integer> searchNode = bsTree.searchRecur(24);
        System.out.println("查找结点24:" + searchNode + ", key值为:" + searchNode.key);
        BSTNode<Integer> searchNonRecurNode = bsTree.searchRecur(24);
        System.out.println("查找结点24:" + searchNonRecurNode + ",key值为：" + searchNonRecurNode.key);

        System.out.println("删除叶子结点72：" + bsTree.remove(72));
        System.out.println("删除叶子结点72：先序遍历");
        bsTree.preOrderRecur();
        System.out.println();
        System.out.println("删除叶子结点72：中序遍历");
        bsTree.inOrderRecur();
        System.out.println();
        System.out.println("删除叶子结点72：后序遍历");
        bsTree.postOrderRecur();
        System.out.println();

        System.out.println("删除结点64：" + bsTree.remove(64));
        System.out.println("删除结点64：先序遍历");
        bsTree.preOrderRecur();
        System.out.println();
        System.out.println("删除结点64：中序遍历");
        bsTree.inOrderRecur();
        System.out.println();
        System.out.println("删除结点64：后序遍历");
        bsTree.postOrderRecur();
        System.out.println();

        System.out.println("删除根结点39：" + bsTree.remove(39));
        System.out.println("删除根结点39：先序遍历");
        bsTree.preOrderRecur();
        System.out.println();
        System.out.println("删除根结点39：中序遍历");
        bsTree.inOrderRecur();
        System.out.println();
        System.out.println("删除根结点39：后序遍历");
        bsTree.postOrderRecur();
        System.out.println();

        // 销毁二叉树
        System.out.println("销毁二叉树");
        bsTree.clear();
        System.out.println("销毁后打印");
        bsTree.print();
    }
}















